package 牛客_面试必刷.Month07.day10;

import java.util.ArrayList;

public class 按之字形顺序打印二叉树 {
    ArrayList<ArrayList<Integer>> list = new ArrayList();
    int treeHeight = 1;//标记当前已经排好了的树的层次
    public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
        if(pRoot == null) return list;
        levelOrder(pRoot,1);
        return list;
    }

    public void levelOrder(TreeNode root,int height){
        //如果说节点来到了一个新的层次，list就进行扩充
        if(height >= treeHeight){
            list.add(new ArrayList());
            treeHeight++;
        }
        //如果是奇数层次，就从左往右，如果是偶数层次就从右往左
        //所以这里就是对height判断一下就好啦，无非就是头插和尾插
        if((height) % 2 != 0){
            list.get(height - 1).add(root.val);
        }else{
            list.get(height - 1).add(0,root.val);
        }
        if(root.left != null) levelOrder(root.left,height + 1);
        if(root.right != null) levelOrder(root.right,height + 1);
    }
}
